UVa/10278 - Fire station/10278.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <cassert>
   8 #include <climits>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <string>
  12 #include <cstdio>
  13 #include <vector>
  14 #include <cmath>
  15 #include <queue>
  16 #include <deque>
  17 #include <stack>
  18 #include <list>
  19 #include <map>
  20 #include <set>
  21
  22 template <class T> string toStr(const T &x){ stringstream s; s << x; return s.str(); }
  23 template <class T> int toInt(const T &x){ stringstream s; s << x; int r; s >> r; return r; }
  24
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  27 #define D(x) cout << #x " is " << x << endl
  28
  29 const int MAXN = 505, oo = 1000000000;
  30 bool fire[MAXN];
  31 int g[MAXN][MAXN];
  32
  33 int main(){
  34   string s;
  35   int casos;
  36   getline(cin, s);
  37   casos = toInt(s);
  38   getline(cin, s);
  39   while (casos--){
  40     string input;
  41     while (getline(cin, s) && s != ""){
  42       input += " " + s;
  43     }
  44     stringstream sin(input);
  45
  46     int f, n;
  47     sin >> f >> n;
  48     For(i, 0, n){
  49       fire[i] = 0;
  50       For(j, 0, n){
  51         g[i][j] = oo;
  52       }
  53       g[i][i] = 0;
  54     }
  55     For(k, 0, f){
  56       int u;
  57       sin >> u;
  58       fire[--u] = true;
  59     }
  60     int u, v, w;
  61     while (sin >> u >> v >> w){
  62       --u, --v;
  63       g[u][v] = min(g[u][v], w);
  64       g[v][u] = min(g[v][u], w);
  65     }
  66
  67     For(k, 0, n){
  68       For(i, 0, n){
  69         For(j, 0, n){
  70           g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
  71         }
  72       }
  73     }
  74
  75     /*
  76     For(i, 0, n){
  77       For(j, 0, n){
  78         printf("%d ", g[i][j]);
  79       }
  80       puts("");
  81     }
  82     */
  83
  84     int which = 0, howmuch = oo;
  85     For(i, 0, n){
  86       if (fire[i]) continue;
  87       //printf("trying to place a station at %d\n", i);
  88       fire[i] = true;
  89       int distance = -1;
  90       For(j, 0, n){
  91         int cur = oo;
  92         For(k, 0, n){
  93           if (fire[k]){
  94             cur = min(cur, g[j][k]);
  95           }
  96         }
  97         //printf("  closest station from node %d is at %d\n", j, cur);
  98         distance = max(distance, cur);
  99       }
 100       if (distance < howmuch){
 101         which = i;
 102         howmuch = distance;
 103       }
 104       fire[i] = false;
 105     }
 106     cout << which + 1 << endl;
 107     if (casos > 0) cout << endl;
 108   }
 109   return 0;
 110 }